package 单周赛.september;

import java.util.Arrays;

/**
 * @
 * @date 2024/06/23
 */
public class 第403场单周赛 {

    public static void main(String[] args) {

    }

    /**
     * 排序+双指针
     */
    public double minimumAverage(int[] nums) {
        double min = Double.MAX_VALUE;
        Arrays.sort(nums);
        int left = 0, right = nums.length - 1;

        while (left < right) {
            min = Math.min(min, (nums[left] + nums[right]) / 2D);
            left++;
            right--;
        }
        return min;
    }

    /**
     * 找最 上下左右 的边界
     */
    public int minimumArea(int[][] grid) {

        int top = Integer.MAX_VALUE, botton = 0;
        int left = Integer.MAX_VALUE, right = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {

                if (grid[i][j] == 1) {

                    top = Math.min(top, i);
                    botton = Math.max(botton, i);

                    left = Math.min(left, j);
                    right = Math.max(right, j);

                }

            }
        }

        return (botton - top + 1) * (right - left + 1);

    }

    /**
     * 动态规划
     * 分隔只要考虑 [0,i-1] [i,i] 和 [0,i-2] [i-1,i] 的情况？
     */
    public long maximumTotalCost(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        long[] dp = new long[nums.length];
        Arrays.fill(dp, Long.MIN_VALUE);
        dp[0] = nums[0];
        dp[1] = Math.max(0L + nums[0] + nums[1], 0L + nums[0] + nums[1] * -1);
        if (nums.length == 2) {
            return dp[1];
        }

        for (int i = 2; i < nums.length; i++) {

            dp[i] = Math.max(dp[i], dp[i - 1] + nums[i]);

            dp[i] = Math.max(dp[i], dp[i - 2] + nums[i - 1] + nums[i] * -1);

        }

        return dp[dp.length - 1];
    }


}
